/*
给你一个链表的头节点 head ，判断链表中是否有环

为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

提示：
    链表中节点的数目范围是 [0, 10^4]
    -10^5 <= Node.val <= 10^5
    pos 为 -1 或者链表中的一个 有效索引 
 

进阶：用 O(1)（即，常量）内存解决此问题


来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "common.h"

#include <stdbool.h>    // C99 标准不包含 bool

/*
解题思路：

假设有两个指针，分别为快慢指针fast和slow, 快指针每次走两步，慢指针每次前进一步，如果有环则两
个指针必定相遇；

A:链表起点
B:环起点
C:相遇点
X:环起点到相遇点距离
Y:链表起点到环起点距离
R：环的长度
S:第一次相遇时走过的路程

慢指针slow第一次相遇走过的路程 S1 = Y + X;（1）
快指针fast第一次相遇走过的路程 S2=2S1 = Y + X + NR;（2）
    说明：快指针的速度是慢指针的两倍，相同时间内路程应该是慢指针的两倍，
            Y + X + NR是因为快指针可能经过N圈后两者才相遇；

把（1）式代入（2）式得：Y = NR -X;
表明头节点和C点的慢指针会在B点相遇，此处就是环节点

*/
bool hasCycle(struct ListNode *head) {
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            fast = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow; // 环节点
       }
    }
    return NULL;
}